import collections


# 动态规划
# class Solution(object):
#     def lengthOfLIS(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: int
#         """
#         n = len(nums)
#         DP = [1] * n
#         for i in range(1, n):
#             for j in range(0, i):
#                 if nums[j] < nums[i]:
#                     DP[i] = max(DP[i], DP[j] + 1)
#         return max(DP)

# 贪心加二分查找
class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        stack = collections.deque()
        stack.append(nums[0])
        length = 1
        for item in nums[1:]:
            if item > stack[-1]:
                stack.append(item)
                length += 1
            else:
                left_index = 0
                right_index = length - 1
                while right_index - left_index >= 2:
                    mid_index = (right_index + left_index) // 2
                    if stack[mid_index] > item:
                        right_index = mid_index
                    else:
                        left_index = mid_index
                if left_index == right_index:
                    stack[left_index] = item
                else:
                    if stack[left_index] >= item:
                        stack[left_index] = item
                    else:
                        stack[right_index] = item
        return length


data = Solution()
nums = [7, 7, 7, 7, 7]
print(data.lengthOfLIS(nums))
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(data.lengthOfLIS(nums))
nums = [0, 1, 0, 3, 2, 3]
print(data.lengthOfLIS(nums))
